package offer_test_20;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

//斐波拉契数列 n=0 0 n=1 1    n>1 f(n-1)+f(n-2)
public class night_Fibonacci {
	public static void main(String[] args) throws IOException {
		// int input;
		// BufferedReader br=new BufferedReader(new
		// InputStreamReader(System.in));
		// String str=br.readLine();
		// input=Integer.parseInt(str);
	}

	// 很不实用的方法，计算速度非常慢，很多重复的计算
	public static int math(int num) {
		if (num == 0) {
			return 0;
		} else if (num == 1) {
			return 1;
		} else {
			return math(num - 1) + math(num - 2);
		}
	}

	// 时间复杂度为On
	public static long math2(int num) {
		long rs = 0;
		long[] rs_array = { 0, 1 };
		if (num < 2) {
			rs = rs_array[num];
		} else {
			long one = 0;
			long two = 1;
			for (int i = 2; i < num; i++) {
				rs = one + two;
				one = two;
				two = rs;
			}
		}
		return rs;
	}
}
